【数据结构】二叉树遍历（递归遍历和非递归遍历） |
您所在的位置：网站首页 › 树 非递归 › 【数据结构】二叉树遍历（递归遍历和非递归遍历） |
【数据结构】二叉树遍历（递归遍历和非递归遍历）
|
学而不思则罔，思而不学则殆 【数据结构】二叉树遍历（递归遍历和非递归遍历） 二叉树递归遍历递归前序遍历递归中序遍历递归后序遍历 非递归遍历前序遍历第一种解法第二种解法 中序遍历思路图解算法过程算法 后续遍历算法思想算法图解算法 层次遍历二叉树相关学习的网站 二叉树定义：每个节点最多有两个子树的数成为二叉树 递归遍历 public class TreeNode { TreeNode left; TreeNode right; char values; public TreeNode(char values) { this.values = values; } } 递归前序遍历 static void preOrder(TreeNode r) { if (r != null) { System.out.print(r.values); preOrder(r.left); preOrder(r.right); } } 递归中序遍历 static void InOrder(TreeNode r) { if (r != null) { InOrder(r.left); System.out.print(r.values); InOrder(r.right); } } 递归后序遍历 static void PostOrder(TreeNode r) { if (r != null) { PostOrder(r.left); PostOrder(r.right); System.out.print(r.values); } }三种递归遍历中，递归遍历左子树和右子树的顺序时固定的，只是访问根节点的顺序不同。不管采取那种遍历方法，每个节点都访问一次且只访问一次。因此时间复杂度为 O ( n ) O(n) O(n) 在递归遍历工作栈的栈深恰好是树的深度，所以在最坏的情况下，（比如单边树），二叉树的有n个节点且深度为n的单支树，遍历算法的空间复杂度为: O ( n ) O(n) O(n) 非递归遍历 前序遍历使用栈作为辅助工具。 第一种解法 static void nonRecursivePre(TreeNode root) { Stack stack = new Stack(); if (root == null) { System.out.println("root == null"); return; } stack.push(root); while (!stack.empty()){ TreeNode treeNode = stack.pop(); //访问节点 System.out.print(treeNode.values); //右子树入栈 if (treeNode.right != null){ stack.push(treeNode.right); } //左子树入栈 if (treeNode.left != null){ stack.push(treeNode.left); } } System.out.println(); } 第二种解法 static void nonRecursivePre2(TreeNode root) { Stack stack = new Stack(); TreeNode treeNode = root; while (treeNode != null || !stack.empty()) { //栈不为空或者treeNode不为null时循环 if (treeNode != null) { //一路向左走到底 System.out.print(treeNode.values); //入栈前访问 stack.push(treeNode); //入栈 treeNode = treeNode.left; //左孩子不为空，一直向左走 } else { //出栈，并转向出栈节点的右孩子 treeNode = stack.pop(); //出栈 treeNode = treeNode.right; //向右子树走，treeNode指向为当前节点的右孩子 } } System.out.println(); } 中序遍历 思路 沿着跟的左孩子，依次入栈，直到左孩子为空，说明已经找到可以输出的节点栈顶元素出栈继续访问：若其右孩子为空，继续执行2,其右孩子不为空，则将右子树执行1 图解算法过程开始时二叉树如下：栈内数据为空 后续非递归遍历二叉树是先访问左子树，在访问右子树，最后访问根节点。 1.沿着根的左孩子，依次入队，直到左孩子为空 2.读栈顶元素：若其右孩子不空，且未被访问过，将右子树转执行1；否则栈顶元素出栈并访问。 结合一个例子来分析： 算法图解初始是如下： 3.此时栈顶元素是B,B的右孩子不空且未被访问过，E入栈 8 栈顶A的右孩子不为空但是已被访问过，A出栈并访问。 在上出算法的第二步中，必须分清返回时是从左子树还是从右子树返回的，因此需要一个辅助指针，指向最近被访问的节点。 算法 //非递归后序遍历 static void nonRecursivePost(TreeNode root) { Stack stack = new Stack(); TreeNode treeNode = root; TreeNode lastVisit = null; while (treeNode != null || !stack.empty()) { //栈不为空或者treeNode不为null时循环 if (treeNode != null) { //一路向左走到底 stack.push(treeNode); //入栈 treeNode = treeNode.left; //左孩子不为空，一直向左走 } else { //出栈，并转向出栈节点的右孩子 treeNode = stack.peek(); //读取栈顶元素，注意不是出栈 if (treeNode.right != null && lastVisit != treeNode.right) { //右子树存在且未被访问过 treeNode = treeNode.right; //转向右子树 stack.push(treeNode); //入栈 treeNode = treeNode.left; //在走到最左 } else { treeNode = stack.pop(); //出栈 System.out.print(treeNode.values); //访问该节点 lastVisit = treeNode; //记录最近访问的节点 treeNode = null; //节点访问完后,置为null } } } System.out.println(); } 层次遍历辅助队列。 二叉树根节点入队，然后出队访问节点，若存在左子树，左子树入队；若存在右子树，右子树入队。然后出队，…知道队列为空。 //辅助队列 static void levelOrder(TreeNode root) { ArrayDeque deque = new ArrayDeque(); if (root == null) { return; } deque.add(root); while (!deque.isEmpty()) { TreeNode treeNode = deque.pop(); System.out.print(treeNode.values); if (treeNode.left != null) { deque.add(treeNode.left); } if (treeNode.right != null) { deque.add(treeNode.right); } } System.out.println(); } 二叉树相关学习的网站动画展示二叉树 https://visualgo.net/zh/bst 二叉树动画展示 http://btv.melezinek.cz/binary-search-tree.html 各种数据结构 动画总结 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html |
沿着这左子树入栈，一直到D，此时栈顶为D,D的左孩子为null. 
D出栈，并访问D.treeNode 指向D的右孩子 
由于D右孩子为空，treeNode 为空，那么就继续执行2，出栈操作。此时出栈B.访问B.treeNode 指向B的右孩子E 
下一次循环，由于treeNode 指向E,所以E入栈，treeNode 指向E的左孩子 
下一次循环：E的左孩子为空，所以treeNode 为空，所以E出栈，并访问，treeNode 指向E的右孩子 
下一次循环的时候，treeNode 指向E的右孩子为空，所有继续出栈，此时A出栈并访问。treeNode 指向A的右孩子C 
下一次循环treeNode 指向A的右孩子C，所以C入栈，treeNode 指向C的左孩子 
下一次循环，由于treeNode 指向C的左孩子为空，所以C出栈，并访问C,treeNode 再指向C的右孩子 
下一次循环，treeNode 再指向C的右孩子的为空，且栈也为空，退出整个遍历，结束。 下面是算法。
1.沿着根的左孩子，依次入队，直到左孩子为空，此时栈内元素为ABD. 
2.此时栈顶元素D右孩子为空，出栈并访问 
4.E的左孩子为空，且右孩子为空。出栈并访问。 
5.此时栈顶元素B的右孩子不为空，但是已经访问过，B出栈并访问。 
6.A栈顶元素，A的右孩子不为空，且未被访问过，C入栈 
7.栈顶C的左右孩子都为空，出栈并访问 
【本文地址】
今日新闻 |
推荐新闻 |